Network service providers enable data communication services using networks interconnected via switches and routing devices including provider edge (PE) routers and customer edge (CE) routers. Customer edge routers communicatively couple customer equipment (e.g., computers and other processor systems, local routers, and local switches) to wide area networks (WANs) via PE routers. Provider edge routers are communicatively coupled to other PE routers across a WAN to enable communication between local CE routers (e.g., CE routers coupled to a particular PE router) and remote CE routers (e.g., CE routers coupled to different PE routers). To deliver data, each PE router is provided with routes (e.g., network paths) that can be used to forward data packets based on destination addresses stored therein. A PE router stores each route in a routing table, and retrieves that route from the routing table each time the PE router receives a data packet having a destination address matching the destination address associated with that route.
As service providers expand their networks, additional routes are brought on line to enable data communications with the new portions of the network. Each time an additional route is created, PE routers to which that route is relevant must store the route in their routing tables. As the quantity of routes increase, so do the requirements for memory capacity to store those routes in each router.
Enterprise customers having multiple locations or sites are increasingly adopting multi-protocol label switching (MPLS)-based virtual private network (VPN) services to implement communication networks among their respective sites via a service provider's network. Such MPLS-based VPNs provide direct any-to-any reachability among sites of the enterprise.